package com.mj.listen1._14_Trie;

import java.util.HashMap;

public class Trie<V> {
    private int size;
    private Node<V> root;

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return false;
    }

    public void clear() {
        size = 0;
        root = null;
    }

    public V get(String key) {
        Node<V> node = node(key);
        return node != null && node.word ? node.value : null;
    }

    public boolean contains(String key) {
        Node<V> node = node(key);
        return node != null && node.word;
    }

    public V add(String key, V value) {
        keyCheck(key);
        if (root == null) {
            root = new Node<>(null);
        }

        Node<V> node = root;
        int len = key.length();
        for (int i = 0; i < len; i++) {
            if (node.childrenNodeMap == null) {
                node.childrenNodeMap = new HashMap<>();
            }
            char c = key.charAt(i);
            Node<V> childNode = node.childrenNodeMap.get(c);
            if (childNode == null) {
                childNode = new Node<>(node);
                childNode.character = c;
                node.childrenNodeMap.put(c, childNode);
            }
            // 找最后一个字符对应的节点
            node = childNode;
        }

        // 校验
        if (node.word) {
            // 已经存在
            V oldValue = node.value;
            node.value = value;
            return oldValue;
        }

        // 新增加一个单词
        size++;
        node.word = true;
        node.value = value;
        return null;
    }

    public V remove(String key) {
        // 找到key对应的节点
        Node<V> node = node(key);
        // 没有找到或者删除的key不是单词
        if (node == null || !node.word) {
            return null;
        }

        size--;

        V oldValue = node.value;

        // 不是最后一个节点，节点后边还有其他节点，节点颜色置为蓝色
        if (node.childrenNodeMap != null && !node.childrenNodeMap.isEmpty()) {
            node.word = false;
            return oldValue;
        }

        // 是最后一个节点，循环依次往上删除节点
        Node<V> parent = null;
        while (node.parent != null) {
            parent = node.parent;
            parent.childrenNodeMap.remove(node.character);
            // 父节点删除自己之后，还存在其他子节点，则停止删除；若父节点是其他单词的尾节点，则停止删除
            if (parent.word || !parent.childrenNodeMap.isEmpty()) break;
            node = parent;
        }

        return oldValue;
    }

    public boolean startsWith(String key) {
        Node<V> node = node(key);
        return node != null;
    }

    /**
     * 给一个字符串，找出这个字符串对应的最后的节点
     *
     * @param key
     * @return
     */
    private Node<V> node(String key) {
        keyCheck(key);
        // 遍历
        Node<V> node = root;
        int len = key.length();
        for (int i = 0; i < len; i++) {
            if (node == null || node.childrenNodeMap == null || node.childrenNodeMap.isEmpty()) {
                return null;
            }
            // 说明不为空
            char c = key.charAt(i);
            // 一直往下找
            node = node.childrenNodeMap.get(c);
        }
        return node;
    }

    private void keyCheck(String key) {
        if (key == null || key.length() == 0) {
            throw new IllegalArgumentException("参数不能为空");
        }
    }

    // 设计Tree的Node节点
    private static class Node<V> {
        // 为删除添加
        Node<V> parent;
        // 为了删除方便添加，当前节点存储的key
        Character character;
        // 该节点下面有多少孩子使用map存储
        HashMap<Character, Node<V>> childrenNodeMap;
        // value,value只存储在找到单词的那个
        V value;
        // 是否是单测结束节点
        boolean word;

        public Node(Node<V> parent) {
            this.parent = parent;
        }
    }
}
